package com.example.demo.algorithm;

import java.util.Arrays;

public class AllSortMethod {
    public static void main(String[] args) {
        int arr[]=new int[]{5,6,3,2,8,9,1,5};
        method1(arr);
        arr=new int[]{5,6,3,2,8,9,1,5};
        method2(arr);
        arr=new int[]{5,6,3,2,8,9,1,5};
        method3(arr);
        arr=new int[]{5,6,3,2,8,9,1,5};
        method4(arr);
        arr=new int[]{5,6,3,2,8,9,1,5};
//         5 5 3 2 8 9 1 6
//            5 5 3 2 1 9 8 6
//            1 5 3 2 5 9 8 6
//            1 2 3 5 5 6 8 9
        method5(arr,0,arr.length-1);
        System.out.println("快速:"+Arrays.toString(arr));
        arr=new int[]{5,6,3,2,8,9,1,5};
        method6(arr,0,arr.length-1);
        System.out.println("归并:"+Arrays.toString(arr));
    }
    public static void method1(int arr[]){
        for(int i = 0;i<arr.length-1;i++){
            boolean b= false;
            for(int j = 0;j<arr.length-i-1;j++){
                if(arr[j] > arr [j+1]){
                    arr[j]=arr[j]^arr [j+1];
                    arr[j+1]=arr[j]^arr [j+1];
                    arr[j]=arr[j]^arr [j+1];
                    b=true;
                }
            }
            if(!b){
                break;
            }
        }
        System.out.println("冒泡:"+Arrays.toString(arr));
    }
    public static void method2(int arr[]){
        for(int i = 0;i<arr.length-1;i++){
             int k= i;
            for(int j = i+1;j<arr.length;j++){
                if(arr[j] < arr[k]){
                    k=j;
                }
            }
            int n = arr[k];
            arr[k] = arr[i];
            arr[i] = n;
        }
        System.out.println("选择:"+Arrays.toString(arr));
    }
    public static void method3(int arr[]){
        for(int i = 1;i<arr.length;i++){
            int currVal = arr[i];
            int index = i;
            while(index-1>=0 && currVal < arr[index-1]){
                arr[index] = arr[index-1];
                index--;
            }
            arr[index] = currVal;
        }
        System.out.println("插入:"+Arrays.toString(arr));
    }


    public static void method4(int arr[]){
        for(int e = arr.length/2;e > 0;e/=2) {
            for (int i = e; i < arr.length; i+=e) {
                int currVal = arr[i];
                int index = i;
                while (index - e >= 0 && currVal < arr[index - e]) {
                    arr[index] = arr[index - e];
                    index-=e;
                }
                arr[index] = currVal;
            }
        }
        System.out.println("希尔:"+Arrays.toString(arr));
    }

    public static void method5(int arr[],int left ,int right){
        int l = left+1;
        int r = right;
        int target = arr[left];
        while(l<r){
            while(l<r && target<=arr[r]){
                r--;
            }
            while(l<r && target>=arr[l]){
                l++;
            }
            if(l!=r){
                arr[l] = arr[l]^arr[r];
                arr[r] = arr[l]^arr[r];
                arr[l] = arr[l]^arr[r];
            }
        }
        arr[left]=arr[l];
        arr[l] = target;
        if(left < l-1){
            method5(arr,left,l-1);
        }
        if(right > l+1){
            method5(arr,l+1,right);
        }

    }
    public static void method6(int arr[],int left ,int right){
        if(left>=right){
            return;
        }
       int mid= (right-left)/2+left;
        method6(arr,left,mid);
        method6(arr,mid+1,right);
        sort(arr,left,right);
    }

    private static void sort(int[] arr, int left, int right) {
        int mid= (right-left)/2+left +1;
        int l=left;
        int r=mid;
        int t=0;
        int rs[]=new int[right-left+1];
        while(l<mid && r<=right){
            if(arr[l]<arr[r]){
                rs[t++]=arr[l++];
            }else {
                rs[t++]=arr[r++];
            }
        }
        while (l<mid){
            rs[t++]=arr[l++];
        }
        while(r<=right){
            rs[t++]=arr[r++];
        }
        int index=0;
        for(int i = left ;i<=right;i++){
            arr[i]=rs[index++];
        }
    }
}
